/*************************************************************************
*File Name: nonRecursivePreOrder.cpp
*Author: Leihang
*mail: 973331055@qq.com
*Created Time: Thu 06 Aug 2020 10:35:36 PM CST
*describe: 
************************************************************************/
#include "binaryNode.h"
#include <iostream>
#include <string>
#include <stack>
using namespace std;
//非递归后序遍历
//1.和前中序不同的是，如果从左子树返回，我们还不能输出节点
//从右子树返回再输出节点。具体做法是设置一个标志，用来标记当前节点是从左子树还是右子树返回
//从左子树返回时，标记设置为2，并进入右子树
void nonRecursivePostOrder(Node* root)
{
    stack<Node*> sta;
    int top=-1;
    int flagStack[5];
    while(root!=NULL||!sta.empty())
    {
        if(root!=NULL)
        {
            sta.push(root);
            ++top;
            flagStack[top]=1;
            root=root->left;
        }
        else
        {
            root=sta.top();
            if(flagStack[top]==1)
            {
                flagStack[top]=2;
                root=root->right;
            }
            else if(flagStack[top]==2)
            {
                cout<<root->val<<" ";
                sta.pop();
                --top;
                root=NULL;
            }
        }
    }
}
int main()
{
    
    int arr[] = {4,1,3,2,5};
    Node* root = NULL;
    for(int i=0;i<5;i++)
    {
        root = build(root,arr[i]);
    }
    nonRecursivePostOrder(root);
    return 0;
}

